#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/**
 * 计算第n个卡特兰数（1-based索引，n≥1）
 * 递推公式：C(0)=C(1)=1，C(n) = Σ(C(k)×C(n-1-k)) （k从0到n-1）
 * 对应Python逻辑：array[i] += array[j] * array[i-j-1]
 * @param n: 卡特兰数的项数（1-based）
 * @return: 第n个卡特兰数（uint64_t类型，支持n≤19，避免溢出）
 */
uint64_t catalan(uint32_t n) {
    // 边界条件：n=1、n=2 时返回1（对应Python n<3返回1）
    if (n < 3) {
        return 1;
    }

    // 动态数组存储中间结果（对应Python的array = [0]*n）
    uint64_t* array = (uint64_t*)calloc(n, sizeof(uint64_t));
    if (!array) {
        fprintf(stderr, "内存分配失败！\n");
        exit(EXIT_FAILURE);
    }

    // 初始化：array[0] = array[1] = 1（对应Python array[0]=array[1]=1）
    array[0] = 1;
    array[1] = 1;

    // 外层循环：从第2项（i=2）计算到第n-1项（i=n-1），对应Python range(2, n)
    for (uint32_t i = 2; i < n; i++) {
        array[i] = 0; // 初始化当前项为0
        // 内层循环：j从0到i-1，累加 array[j] * array[i-j-1]
        for (uint32_t j = 0; j < i; j++) {
            array[i] += array[j] * array[i - j - 1];
        }
    }

    // 第n个卡特兰数存储在array[n-1]（对应Python return array[n-1]）
    uint64_t result = array[n - 1];
    free(array); // 释放动态数组，避免内存泄漏
    return result;
}

// 测试主函数（与Python测试用例完全一致）
int main() {
    uint32_t test_nums[] = {1, 2, 3, 4, 5, 6};
    uint32_t test_count = sizeof(test_nums) / sizeof(test_nums[0]);

    printf("卡特兰数测试结果：\n");
    for (uint32_t i = 0; i < test_count; i++) {
        uint32_t n = test_nums[i];
        uint64_t cat = catalan(n);
        printf("catalan(%d) = %llu\n", n, cat);
    }

    // 额外测试第7项卡特兰数（预期42×2+14=132）
    uint32_t extra_n = 7;
    uint64_t extra_cat = catalan(extra_n);
    printf("catalan(%d) = %llu\n", extra_n, extra_cat);

    return 0;
}